#pragma once
#include<assert.h>
namespace myself
{
	template<class T>
	struct ListNode
	{
		struct ListNode<T>* _next;
		struct ListNode<T>* _prev;
		T _val;
		ListNode(const T& val = T())
			:_next(nullptr), _prev(nullptr), _val(val)
		{

		}
	};
	template<class T,class Ref ,class Ptr>
	struct Listiterator
	{
		typedef ListNode<T> Node;
		typedef Listiterator<T,Ref,Ptr> Self;
		Node* _node;
		Listiterator(Node* n)
		{
			_node = n;
		}
		//T&
		Ref	operator*()
		{
			return _node->_val;
		}
		//T*
		Ptr operator->()
		{
			return  &_node->_val;
		}
		bool operator !=(const Self&n)
		{
			return _node!=n._node;
		}
		bool operator ==(const Self& n)
		{
			return _node == n._node;
		}
		Self& operator++()
		{
			_node=_node->_next;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp(_node);
			_node = _node->_next;
			return tmp;
		}
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		Self operator--(int)
		{
			Self tmp(_node);
			_node = _node->_prev;
			return tmp;
		}
	};
	//template<class T>
	//struct const_Listiterator
	//{
	//	typedef ListNode<T> Node;
	//	typedef const_Listiterator<T> Self;
	//	Node* _node;
	//	const_Listiterator(Node* n)
	//	{
	//		_node = n;
	//	}
	//	const T& operator*()
	//	{
	//		return _node->_val;
	//	}
	//	const T* operator->()
	//	{
	//		return  &_node->_val;
	//	}
	//	bool operator !=(const Self& n)
	//	{
	//		return _node != n._node;
	//	}
	//	bool operator ==(const Self& n)
	//	{
	//		return _node == n._node;
	//	}
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	Self operator++(int)
	//	{
	//		Self tmp(_node);
	//		_node = _node->_next;
	//		return tmp;
	//	}
	//	Self& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}
	//	Self operator--(int)
	//	{
	//		Self tmp(_node);
	//		_node = _node->_prev;
	//		return tmp;
	//	}
	//};
	template<class T>
	class List
	{
	public:
		typedef Listiterator<T,T&,T*> iterator;
		typedef Listiterator<T,const T&,const T*> const_iterator;
		typedef ListNode<T> Node;
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator cbegin()const
		{
			return const_iterator(_head->_next);
		}
		const_iterator cend()const
		{
			return const_iterator(_head);
		}
		List()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		void PushBack(const T& val)
		{
			/*Node* newnode = new Node(val);
			Node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
			_size++;*/
			insert(end(),val);
			_size++;
		}
		void PushFront(const T& val)
		{
			/*Node* head = _head->_next;
			Node* newnode = new Node(val);
			head->_prev = newnode;
			newnode->_next = head;
			newnode->_prev = _head;
			_head->_next = newnode;
			_size++;*/
			insert(begin(), val);
			_size++;
		}
		bool Empty()
		{
			return _size == 0;
		}
		void PopBack()
		{
		    assert(!Empty());
			/*Node* tail = _head->_prev;
			tail->_prev->_next = _head;
			_head->_prev = tail->_prev;
			tail->_next = nullptr;
			tail->_prev = nullptr;
			tail->_val = 0;*/
			Erase(--end());
		}
		void PopFront()
		{
			assert(!Empty());
			/*Node* head = _head->_next;
			_head->_next = head->_next;
			head->_next->_prev = _head;
			head->_next = nullptr;
			head->_prev = nullptr;
			head->_val = 0;*/
			Erase(begin());
		}
		iterator find(const T& x)
		{
			List<T>::iterator it1 = begin();
			while (it1 != end())
			{
				if (*it1 == x)
				{
					return it1;
				}
				it1++;
			}
			return nullptr;
		}
		const_iterator cfind(const T& x)const
		{
			List<T>::const_iterator it1 = cbegin();
			while (it1 != cend())
			{
				if (*it1 == x)
				{
					return it1;
				}
				it1++;
			}
			return nullptr;
		}
		void insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x);
			Node* node = pos._node;
			Node* prev = node->_prev;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = node;
			node->_prev = newnode;
		}
		iterator Erase(iterator pos)
		{	
			Node* node = pos._node;
			Node* prev = node->_prev;
			Node* next = node->_next;
			prev->_next = next;
			next->_prev = prev;
			delete node;
			_size--;
			return iterator(next);
		}
		void Clear()
		{
			List<T>::iterator it1 = begin();
				while (it1 != end())
				{
					it1 = Erase(it1);
				}
		}
		~List()
		{
			Clear();
			delete _head;
			_head = nullptr;
		}
		size_t size()const
		{
			return size;
		}
	/*	~List()
		{
			ListNode<T>::iterator  =it1 = end();
			while (it1 != begin())
			{
				Node* node = it1._node;
				Node* prev = node->_prev;
				node->_next = nullptr;
				node->_prev = nullptr;
				node->_val = 0;
				delete[]node;
				it1 = prev;
			}
		}*/
	private:
		Node* _head;
		size_t _size;
	};
}
void test4()
{
	myself::List<int> L1;
	L1.PushBack(1);
	L1.PushBack(2);
	L1.PushBack(3);
	L1.PushBack(4);
	//myself::List<int>::iterator it = L1.find(666);
	myself::List<int>::iterator it = L1.find(4);
	L1.insert(it, 999);
	myself::List<int>::iterator it1 = L1.begin();

	while (it1 != L1.end())
	{
		std::cout << *it1 << " ";
		it1++;
	}
	std::cout << std::endl;
}
void test3()
{
	myself::List<int> L1;
	L1.PushBack(1);
	L1.PushBack(2);
	L1.PushBack(3);
	L1.PushBack(4);
	myself::List<int>::const_iterator it = L1.cfind(666);
	
	if (it != nullptr)
	{
		std::cout << *it << std::endl;
	}
	else
		std::cout << "no this date" << std::endl;
}

void test1()
{
	myself::List<int> L1;
	L1.PushBack(1);
	L1.PushBack(2);
	L1.PushBack(3);
	L1.PushBack(4);
	myself::List<int>::const_iterator it1 = L1.cbegin();
	while (it1!=L1.cend())
	{
		
		std::cout << *it1 << " ";
		++it1;
	}
	/*std::cout << std::endl;
	myself::List<int>::iterator it2 = L1.begin();
	while (it2 != L1.end())
	{

		std::cout << *it2 << " ";
		++it2;
	}
	std::cout << std::endl;*/

}
void test2()
{
	myself::List<int> L1;
	L1.PushBack(1);
	L1.PushBack(2);
	L1.PushBack(3);
	L1.PushBack(4);
	myself::List<int>::iterator it1 = L1.begin();
	while (it1 != L1.end())
	{

		std::cout << *it1 << " ";
		++it1;
	}
	std::cout << std::endl;
	L1.PushFront(666);
	L1.PushFront(10086);
	it1 = L1.begin();
	while (it1 != L1.end())
	{

		std::cout << *it1 << " ";
		++it1;
	}
	std::cout << std::endl;

	L1.PopBack();
	L1.PopBack();
	it1 = L1.begin();
	while (it1 != L1.end())
	{

		std::cout << *it1 << " ";
		++it1;
	}
	std::cout << std::endl;
	L1.PopFront();
	L1.PopFront();
	L1.PushBack(1);
	L1.PushBack(2);
	L1.PushBack(3);
	L1.PushBack(4);
	it1 = L1.begin();
	while (it1 != L1.end())
	{

		std::cout << *it1 << " ";
		++it1;
	}
	std::cout << std::endl;

}